CSE408
Floyd and warshal
binomial coff
Lecture # 22
All-Pairs Shortest Path Problem
Suppose we are given a directed graph G=(V,E)
and a weight function w: E->R.
We assume that G does not contain cycles of
weight 0 or less.
The All-Pairs Shortest Path Problem asks to find
the length of the shortest path between any pair
of vertices in G.
2
Quick Solutions
If the weight function is nonnegative for all
edges, then we can use Dijkstra’s single source
shortest path algorithm for all vertices to solve
the problem.
This yields an O(n
3
) algorithm on graphs with n
vertices (on dense graphs and with a simple
implementation).
3
Quick Solution
For arbitrary weight functions, we can use the
Bellman-Ford algorithm applied to all vertices.
This yields an O(n
4
) algorithm for graphs with n
vertices.
4
Floyd-Warshall
We will now investigate a dynamic programming
solution that solved the problem in O(n
3
) time
for a graph with n vertices.
This algorithm is known as the Floyd-Warshall
algorithm, but it was apparently described
earlier by Roy.
5
Representation of the Input
We assume that the input is represented by a
weight matrix W= (w
ij
)
i,j in E
that is defined by
w
ij
= 0 if i=j
w
ij
= w(i,j) if ij and (i,j) in E
w
ij
= if ij and (i,j) not in E
6
Format of the Output
If the graph has n vertices, we return a distance
matrix (d
ij
), where d
ij
the length of the path from
i to j.
7
Intermediate Vertices
Without loss of generality, we will assume that
V={1,2,…,n}, i.e., that the vertices of the graph
are numbered from 1 to n.
Given a path p=(v
1
, v
2
,…, v
m
) in the graph, we
will call the vertices v
k
with index k in {2,…,m-1}
the intermediate vertices of p.
8
Key Definition
The key to the Floyd-Warshall algorithm is the
following definition:
Let d
ij
(k)
denote the length of the shortest path
from i to j such that all intermediate vertices are
contained in the set {1,…,k}.
9
Remark 1
A shortest path does not contain any vertex
twice, as this would imply that the path contains
a cycle. By assumption, cycles in the graph have
a positive weight, so removing the cycle would
result in a shorter path, which is impossible.
10
Remark 2
Consider a shortest path p from i to j such that
the intermediate vertices are from the set
{1,…,k}.
• If the vertex k is not an intermediate vertex on
p, then d
ij
(k)
= d
ij
(k-1)
If the vertex k is an intermediate vertex on p,
then d
ij
(k)
= d
ik
(k-1)
+ d
kj
(k-1)
Interestingly, in either case, the subpaths contain merely nodes
from {1,…,k-1}.
11
Remark 2
Therefore, we can conclude that
d
ij
(k)
= min{d
ij
(k-1)
, d
ik
(k-1)
+ d
kj
(k-1)
}
12
Recursive Formulation
If we do not use intermediate nodes, i.e., when
k=0, then
d
ij
(0)
= w
ij
If k>0, then
d
ij
(k)
= min{d
ij
(k-1)
, d
ik
(k-1)
+ d
kj
(k-1)
}
13
The Floyd-Warshall Algorithm
Floyd-Warshall(W)
n = # of rows of W;
D
(0)
= W;
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
d
ij
(k)
= min{d
ij
(k-1)
, d
ik
(k-1)
+ d
kj
(k-1)
};
od;
od;
od;
return D
(n)
;
14
Time and Space Requirements
The running time is obviously O(n
3
).
However, in this version, the space requirements
are high. One can reduce the space from O(n
3
)
to O(n
2
) by using a single array d.
15
CSE408
Optimal binary search
tree and
Knapsack problem
Lecture # 23
8 -2
Optimal binary search trees
• e.g. binary search trees for 3, 7, 9, 12;
3
7
12
9
(a) (b)
9
3
7
12
12
3
7
9
(c)
12
3
7
9
(d)
8 -3
Optimal binary search trees
• n identifiers : a
1
<a
2
<a
3
<…< a
n
P
i
, 1in : the probability that a
i
is searched.
Q
i
, 0in : the probability that x is searched
where a
i
< x < a
i+1
(a
0
=-, a
n+1
=).
1
11
=+
==
n
i
i
n
i
i
QP
8 -4
• Identifiers : 4, 5, 8, 10, 11,
12, 14
• Internal node : successful
search, P
i
• External node : unsuccessful
search, Q
i
10
14
E
7
5
11
12E
4
4
E
0
E
1
8
E
2
E
3
E
5
E
6
◼The expected cost of a binary tree:
◼The level of the root : 1
==
−+
n
0n
ii
n
1n
ii
1))(level(EQ)level(aP
8 -5
The dynamic programming approach
• Let C(i, j) denote the cost of an optimal binary search
tree containing a
i
,…,a
j
.
• The cost of the optimal binary search tree with a
k
as
its root :
a
k
a
1
...a
k-1
a
k+1
...a
n
P
1
...P
k-1
Q
0
...Q
k-1
P
k+1
...P
n
Q
k
...Q
n
C(1,k-1) C(k+1,n)
( ) ( ) ( ) ( )
+++++
−++++=
+=
−
=
n1,kCQPQ1k1,CQPQPminn)C(1,
n
1ki
iik
1k
1i
ii0k
nk1
8 -6
( ) ( )
( ) ( )
( ) ( ) ( )
+++++−=
+++++
−++++=
=
+=
−
=
j
im
mm1-i
jki
j
1km
mmk
1k
im
mm1-ik
jki
QPQj1,kC1ki,Cmin
j1,kCQPQ
1ki,CQPQPminj)C(i,
General formula
8 -7
Computation relationships of sub trees
• e.g. n=4
• Time complexity : O(n
3
)
when j-i=m, there are (n-m) C(i, j)’s to compute.
Each C(i, j) with j-i=m can be computed in O(m) time.
C(1,4)
C(1,3) C(2,4)
C(1,2) C(2,3) C(3,4)
)O(n)m)m(nO(
3
nm1
=−
Knapsack problem
There are two versions of the problem:
1. “0-1 knapsack problem”
• Items are indivisible; you either take an item or not. Some
special instances can be solved with dynamic programming
2. “Fractional knapsack problem”
• Items are divisible: you can take any fraction of an item
• Given a knapsack with maximum capacity W,
and a set S consisting of n items
• Each item i has some weight w
i
and benefit
value b
i
(all w
i
and W are integer values)
• Problem: How to pack the knapsack to achieve
maximum total value of packed items?
0-1 Knapsack problem
• Problem, in other words, is to find
Ti
i
Ti
i
Wwb subject to max
0-1 Knapsack problem
The problem is called a “0-1” problem,
because each item must be entirely
accepted or rejected.
Let’s first solve this problem with a
straightforward algorithm
• Since there are n items, there are 2
n
possible combinations of items.
• We go through all combinations and find
the one with maximum value and with total
weight less or equal to W
• Running time will be O(2
n
)
0-1 Knapsack problem: brute-force approach
• We can do better with an algorithm based on
dynamic programming
• We need to carefully identify the subproblems
0-1 Knapsack problem: dynamic programming pproach
• Given a knapsack with maximum capacity W,
and a set S consisting of n items
• Each item i has some weight w
i
and benefit
value b
i
(all w
i
and W are integer values)
• Problem: How to pack the knapsack to achieve
maximum total value of packed items?
Defining a Subproblem
• We can do better with an algorithm based on
dynamic programming
• We need to carefully identify the subproblems
Let’s try this:
If items are labeled 1..n, then a subproblem
would be to find an optimal solution for
S
k
= {items labeled 1, 2, .. k}
Defining a Sub problem
CSE408
Matrix Chain
Multiplication
Lecture # 24
11-2
Matrix-chain Multiplication
• Suppose we have a sequence or chain A
1
, A
2
,
…, A
n
of n matrices to be multiplied
– That is, we want to compute the product
A
1
A
2
…A
n
• There are many possible ways
(parenthesizations) to compute the product
11-3
Matrix-chain Multiplication …contd
• Example: consider the chain A
1
, A
2
, A
3
, A
4
of
4 matrices
– Let us compute the product A
1
A
2
A
3
A
4
• There are 5 possible ways:
1. (A
1
(A
2
(A
3
A
4
)))
2. (A
1
((A
2
A
3
)A
4
))
3. ((A
1
A
2
)(A
3
A
4
))
4. ((A
1
(A
2
A
3
))A
4
)
5. (((A
1
A
2
)A
3
)A
4
)
11-4
Matrix-chain Multiplication …contd
• To compute the number of scalar
multiplications necessary, we must know:
– Algorithm to multiply two matrices
– Matrix dimensions
• Can you write the algorithm to multiply two
matrices?
11-5
Algorithm to Multiply 2 Matrices
Input: Matrices A
p×q
and B
q×r
(with dimensions p×q and q×r)
Result: Matrix C
p×r
resulting from the product A·B
MATRIX-MULTIPLY(A
p×q
, B
q×r
)
1. for i ← 1 to p
2. for j ← 1 to r
3. C[i, j] ← 0
4. for k ← 1 to q
5. C[i, j] ← C[i, j] + A[i, k] · B[k, j]
6. return C
Scalar multiplication in line 5 dominates time to compute
CNumber of scalar multiplications = pqr
11-6
Matrix-chain Multiplication …contd
• Example: Consider three matrices A
10100
,
B
1005
, and C
550
• There are 2 ways to parenthesize
– ((AB)C) = D
105
· C
550
• AB 10·100·5=5,000 scalar multiplications
• DC 10·5·50 =2,500 scalar multiplications
– (A(BC)) = A
10100
· E
10050
• BC 100·5·50=25,000 scalar multiplications
• AE 10·100·50 =50,000 scalar multiplications
Total:
7,500
Total:
75,000
11-7
Matrix-chain Multiplication …contd
• Matrix-chain multiplication problem
– Given a chain A
1
, A
2
, …, A
n
of n matrices, where
for i=1, 2, …, n, matrix A
i
has dimension p
i-1
p
i
– Parenthesize the product A
1
A
2
…A
n
such that the
total number of scalar multiplications is
minimized
• Brute force method of exhaustive search
takes time exponential in n
11-8
Dynamic Programming Approach
• The structure of an optimal solution
– Let us use the notation A
i..j
for the matrix that
results from the product A
i
A
i+1
… A
j
– An optimal parenthesization of the product
A
1
A
2
…A
n
splits the product between A
k
and A
k+1
for some integer k where1 ≤ k < n
– First compute matrices A
1..k
and A
k+1..n
; then
multiply them to get the final matrix A
1..n
11-9
Dynamic Programming Approach …contd
– Key observation: parenthesizations of the
subchains A
1
A
2
…A
k
and A
k+1
A
k+2
…A
n
must also be
optimal if the parenthesization of the chain
A
1
A
2
…A
n
is optimal (why?)
– That is, the optimal solution to the problem
contains within it the optimal solution to
subproblems
11-10
Dynamic Programming Approach …contd
• Recursive definition of the value of an
optimal solution
– Let m[i, j] be the minimum number of scalar
multiplications necessary to compute A
i..j
– Minimum cost to compute A
1..n
is m[1, n]
– Suppose the optimal parenthesization of A
i..j
splits the product between A
k
and A
k+1
for some
integer k where i ≤ k < j
11-11
Dynamic Programming Approach …contd
– A
i..j
= (A
i
A
i+1
…A
k
)·(A
k+1
A
k+2
…A
j
)= A
i..k
· A
k+1..j
– Cost of computing A
i..j
= cost of computing A
i..k
+
cost of computing A
k+1..j
+ cost of multiplying A
i..k
and A
k+1..j
– Cost of multiplying A
i..k
and A
k+1..j
is p
i-1
p
k
p
j
– m[i, j ] = m[i, k] + m[k+1, j ] + p
i-1
p
k
p
j
for i ≤
k < j
– m[i, i ] = 0 for i=1,2,…,n
11-12
Dynamic Programming Approach …contd
– But… optimal parenthesization occurs at one
value of k among all possible i ≤ k < j
– Check all these and select the best one
m[i, j ] =
0 if i=j
min {m[i, k] + m[k+1, j ] + p
i-1
p
k
p
j
} if i<j
i ≤ k< j
11-13
Dynamic Programming Approach …contd
• To keep track of how to construct an optimal
solution, we use a table s
• s[i, j ] = value of k at which A
i
A
i+1
… A
j
is split
for optimal parenthesization
• Algorithm: next slide
– First computes costs for chains of length l=1
– Then for chains of length l=2,3, … and so on
– Computes the optimal cost bottom-up
11-14
Algorithm to Compute Optimal Cost
Input: Array p[0…n] containing matrix dimensions and n
Result: Minimum-cost table m and split table s
MATRIX-CHAIN-ORDER(p[ ], n)
for i ← 1 to n
m[i, i] ← 0
for l ← 2 to n
for i ← 1 to n-l+1
j ← i+l-1
m[i, j] ←
for k ← i to j-1
q ← m[i, k] + m[k+1, j] + p[i-1] p[k] p[j]
if q < m[i, j]
m[i, j] ← q
s[i, j] ← k
return m and s
Takes O(n
3
) time
Requires O(n
2
) space
11-15
Constructing Optimal Solution
• Our algorithm computes the minimum-cost
table m and the split table s
• The optimal solution can be constructed
from the split table s
– Each entry s[i, j ]=k shows where to split the
product A
i
A
i+1
… A
j
for the minimum cost
11-16
Example
• Show how to multiply this
matrix chain optimally
• Solution on the board
– Minimum cost 15,125
– Optimal parenthesization
((A
1
(A
2
A
3
))((A
4
A
5
)A
6
))
Matrix Dimension
A
1
30×35
A
2
35×15
A
3
15×5
A
4
5×10
A
5
10×20
A
6
20×25
CSE408
Longest Common Sub
Sequence
Lecture # 25
2
Dynamic programming
• It is used, when the solution can be
recursively described in terms of solutions
to subproblems (optimal substructure)
• Algorithm finds solutions to subproblems
and stores them in memory for later use
• More efficient than “brute-force methods”,
which solve the same subproblems over
and over again
2/27/2024
3
Longest Common Subsequence (LCS)
Application: comparison of two DNA strings
Ex: X= {A B C B D A B }, Y= {B D C A B A}
Longest Common Subsequence:
X = A B C B D A B
Y = B D C A B A
Brute force algorithm would compare each
subsequence of X with the symbols in Y
2/27/2024
4
LCS Algorithm
• if |X| = m, |Y| = n, then there are 2
m
subsequences of x; we must compare each
with Y (n comparisons)
• So the running time of the brute-force
algorithm is O(n 2
m
)
• Notice that the LCS problem has optimal
substructure: solutions of subproblems are
parts of the final solution.
• Subproblems: “find LCS of pairs of prefixes
of X and Y”
2/27/2024
5
LCS Algorithm
• First we’ll find the length of LCS. Later we’ll
modify the algorithm to find LCS itself.
• Define X
i
, Y
j
to be the prefixes of X and Y of
length i and j respectively
• Define c[i,j] to be the length of LCS of X
i
and
Y
j
• Then the length of LCS of X and Y will be
c[m,n]
−−
=+−−
=
otherwise]),1[],1,[max(
],[][ if1]1,1[
],[
jicjic
jyixjic
jic
2/27/2024
6
LCS recursive solution
• We start with i = j = 0 (empty substrings of x
and y)
• Since X
0
and Y
0
are empty strings, their LCS
is always empty (i.e. c[0,0] = 0)
• LCS of empty string and any other string is
empty, so for every i and j: c[0, j] = c[i,0] = 0
−−
=+−−
=
otherwise]),1[],1,[max(
],[][ if1]1,1[
],[
jicjic
jyixjic
jic
2/27/2024
7
LCS recursive solution
• When we calculate c[i,j], we consider two
cases:
• First case: x[i]=y[j]: one more symbol in
strings X and Y matches, so the length of LCS
X
i
and Y
j
equals to the length of LCS of
smaller strings X
i-1
and Y
i-1
, plus 1
−−
=+−−
=
otherwise]),1[],1,[max(
],[][ if1]1,1[
],[
jicjic
jyixjic
jic
2/27/2024
8
LCS recursive solution
• Second case: x[i] != y[j]
• As symbols don’t match, our solution is not
improved, and the length of LCS(X
i
, Y
j
) is the
same as before (i.e. maximum of LCS(X
i
, Y
j-1
)
and LCS(X
i-1
,Y
j
)
−−
=+−−
=
otherwise]),1[],1,[max(
],[][ if1]1,1[
],[
jicjic
jyixjic
jic
Why not just take the length of LCS(X
i-1
, Y
j-1
) ?
2/27/2024
9
LCS Length Algorithm
LCS-Length(X, Y)
1. m = length(X) // get the # of symbols in X
2. n = length(Y) // get the # of symbols in Y
3. for i = 1 to m c[i,0] = 0 // special case: Y
0
4. for j = 1 to n c[0,j] = 0 // special case: X
0
5. for i = 1 to m // for all X
i
6. for j = 1 to n // for all Y
j
7. if ( X
i
== Y
j
)
8. c[i,j] = c[i-1,j-1] + 1
9. else c[i,j] = max( c[i-1,j], c[i,j-1] )
10. return c
10
LCS Example
We’ll see how LCS algorithm works on the
following example:
• X = ABCB
• Y = BDCAB
LCS(X, Y) = BCB
X = A B C B
Y = B D C A B
What is the Longest Common Subsequence
of X and Y?
11
LCS Example (0)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
X = ABCB; m = |X| = 4
Y = BDCAB; n = |Y| = 5
Allocate array c[5,4]
ABCB
BDCAB
12
LCS Example (1)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
for i = 1 to m c[i,0] = 0
for j = 1 to n c[0,j] = 0
ABCB
BDCAB
2/27/2024
13
LCS Example (2)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
0
ABCB
BDCAB
2/27/2024
14
LCS Example (3)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
0 0 0
ABCB
BDCAB
2/27/2024
15
LCS Example (4)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
0 0 0 1
ABCB
BDCAB
2/27/2024
16
LCS Example (5)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
000 1 1
ABCB
BDCAB
2/27/2024
17
LCS Example (6)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
0 0 10 1
1
ABCB
BDCAB
2/27/2024
18
LCS Example (7)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 1 11
ABCB
BDCAB
2/27/2024
19
LCS Example (8)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 1 1 1 2
ABCB
BDCAB
2/27/2024
20
LCS Example (10)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
21 1 11
1 1
ABCB
BDCAB
2/27/2024
21
LCS Example (11)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 21 11
1 1 2
ABCB
BDCAB
2/27/2024
22
LCS Example (12)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 21 1
1 1 2
1
22
ABCB
BDCAB
2/27/2024
23
LCS Example (13)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 21 1
1 1 2
1
22
1
ABCB
BDCAB
2/27/2024
24
LCS Example (14)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 21 1
1 1 2
1
22
1 1 2 2
ABCB
BDCAB
2/27/2024
25
LCS Example (15)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
B
Yj BB ACD
0
0
00000
0
0
0
if ( X
i
== Y
j
)
c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max( c[i-1,j], c[i,j-1] )
1000 1
1 21 1
1 1 2
1
22
1 1 2 2
3
ABCB
BDCAB
2/27/2024
26
LCS Algorithm Running Time
• LCS algorithm calculates the values of each
entry of the array c[m,n]
• So what is the running time?
O(m*n)
since each c[i,j] is calculated in
constant time, and there are m*n
elements in the array
27
How to find actual LCS
• So far, we have just found the length of LCS,
but not LCS itself.
• We want to modify this algorithm to make it
output Longest Common Subsequence of X
and Y
Each c[i,j] depends on c[i-1,j] and c[i,j-1]
or c[i-1, j-1]
For each c[i,j] we can say how it was acquired:
2
2 3
2
For example, here
c[i,j] = c[i-1,j-1] +1 = 2+1=3
2/27/2024
28
How to find actual LCS - continued
• Remember that
−−
=+−−
=
otherwise]),1[],1,[max(
],[][ if1]1,1[
],[
jicjic
jyixjic
jic
So we can start from c[m,n] and go backwards
Whenever c[i,j] = c[i-1, j-1]+1, remember x[i]
(because x[i] is a part of LCS)
When i=0 or j=0 (i.e. we reached the
beginning), output remembered letters in
reverse order
2/27/2024
29
Finding LCS
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
Yj BB ACD
0
0
00000
0
0
0
1000 1
1 21 1
1 1 2
1
22
1 1 2 2
3
B
30
Finding LCS (2)
j 0 1 2 3 4 5
0
1
2
3
4
i
Xi
A
B
C
Yj BB ACD
0
0
00000
0
0
0
1000 1
1 21 1
1 1 2
1
22
1 1 2 2
3
B
B C B
LCS (reversed order):
LCS (straight order): B C B
(this string turned out to be a palindrome)
CSE408
Bubble sort
Maximum & Minimum
Lecture #16
Why Study Sorting Algorithms?
• There are a variety of situations that we can
encounter
– Do we have randomly ordered keys?
– Are all keys distinct?
– How large is the set of keys to be ordered?
– Need guaranteed performance?
• Various algorithms are better suited to some
of these situations
Some Definitions
• Internal Sort
– The data to be sorted is all stored in the
computer’s main memory.
• External Sort
– Some of the data to be sorted might be stored in
some external, slower, device.
• In Place Sort
– The amount of extra space required to sort the
data is constant with the input size.
Bubble Sort
• Idea:
– Repeatedly pass through the array
– Swaps adjacent elements that are out of order
• Easier to implement, but slower than Insertion
sort
1 2 3 n
i
1329648
j
Example
1329648
i = 1 j
3129648
i = 1 j
3219648
i = 1 j
3291648
i = 1 j
3296148
i = 1 j
3296418
i = 1 j
3296481
i = 1 j
3296481
i = 2 j
3964821
i = 3 j
9648321
i = 4 j
9684321
i = 5 j
9864321
i = 6 j
9864321
i = 7
j
Bubble Sort
Alg.: BUBBLESORT(A)
for i 1 to length[A]
do for j length[A] downto i + 1
do if A[j] < A[j -1]
then exchange A[j] A[j-1]
1329648
i = 1 j
i
Bubble-Sort Running Time
Thus,T(n) = (n
2
)
2
2
1 1 1
( 1)
()
2 2 2
n n n
i i i
n n n n
where n i n i n
= = =
+
− = − = − = −
Alg.: BUBBLESORT(A)
for i 1 to length[A]
do for j length[A] downto i + 1
do if A[j] < A[j -1]
then exchange A[j] A[j-1]
T(n) = c
1
(n+1) +
++−
=
n
i
in
1
)1(
c
2
c
3
=
+−
n
i
in
1
)(
c
4
=
−
n
i
in
1
)(
= (n) +
(c
2
+ c
2
+ c
4
)
=
−
n
i
in
1
)(
Comparisons: n
2
/2
Exchanges: n
2
/2
c
1
c
2
c
3
c
4
Selection Sort
• Idea:
– Find the smallest element in the array
– Exchange it with the element in the first position
– Find the second smallest element and exchange it
with the element in the second position
– Continue until the array is sorted
• Disadvantage:
– Running time depends only slightly on the amount
of order in the file
Example
1329648
8329641
8349621
8649321
8964321
8694321
9864321
9864321
Selection Sort
Alg.: SELECTION-SORT(A)
n ← length[A]
for j ← 1 to n - 1
do smallest ← j
for i ← j + 1 to n
do if A[i] < A[smallest]
then smallest ← i
exchange A[j] ↔ A[smallest]
1329648
n
2
/2
comparisons
Analysis of Selection Sort
Alg.: SELECTION-SORT(A)
n ← length[A]
for j ← 1 to n - 1
do smallest ← j
for i ← j + 1 to n
do if A[i] < A[smallest]
then smallest ← i
exchange A[j] ↔ A[smallest]
cost times
c
1
1
c
2
n
c
3
n-1
c
4
c
5
c
6
c
7
n-1
−
=
+−
1
1
)1(
n
j
jn
−
=
−
1
1
)(
n
j
jn
−
=
−
1
1
)(
n
j
jn
n
exchanges
( ) ( )
1 1 1
2
1 2 3 4 5 6 7
1 1 2
( ) ( 1) ( 1) ( 1) ( )
n n n
j j j
T n c c n c n c n j c n j c n j c n n
− − −
= = =
= + + − + − + + − + − + − =
MINIMUM AND MAXIMUM
CSE408
Count, Radix & Bucket
Sort
Lecture #17
2
How Fast Can We Sort?
• Selection Sort, Bubble Sort, Insertion Sort:
• Heap Sort, Merge sort:
• Quicksort:
• What is common to all these algorithms?
– Make comparisons between input elements
a
i
< a
j
, a
i
≤ a
j
, a
i
= a
j
, a
i
≥ a
j
, or a
i
> a
j
O(n
2
)
O(nlgn)
O(nlgn) - average
3
Lower-Bound for Sorting
• Theorem: To sort n elements, comparison sorts must
make (nlgn) comparisons in the worst case.
(see CS477 for a proof)
4
Can we do better?
• Linear sorting algorithms
– Counting Sort
– Radix Sort
– Bucket sort
• Make certain assumptions about the data
• Linear sorts are NOT “comparison sorts”
5
Counting Sort
• Assumptions:
– n integers which are in the range [0 ... r]
– r is in the order of n, that is, r=O(n)
• Idea:
– For each element x, find the number of elements x
– Place x into its correct position in the output array
output array
6
Step 1
(i.e., frequencies)
(r=6)
7
Step 2
C
new
C
(frequencies)
(cumulative sums)
8
Algorithm
• Start from the last element of A
• Place A[i] at its correct place in the output array
• Decrease C[A[i]] by one
30320352
1 2 3 4 5 6 7 8
A
77422
1 2 3 4 5
C
new
8
0
9
Example
30320352
1 2 3 4 5 6 7 8
A
77422
1 2 3 4 5
C
new
8
0
3
1 2 3 4 5 6 7 8
B
76422
1 2 3 4 5
C
new
8
0
30
1 2 3 4 5 6 7 8
B
76421
1 2 3 4 5
C
new
8
0
330
1 2 3 4 5 6 7 8
B
75421
1 2 3 4 5
C
new
8
0
3320
1 2 3 4 5 6 7 8
B
75321
1 2 3 4 5
C
new
8
0
10
Example (cont.)
30320352
1 2 3 4 5 6 7 8
A
33200
1 2 3 4 5 6 7 8
B
75320
1 2 3 4 5
C
8
0
5333200
1 2 3 4 5 6 7 8
B
74320
1 2 3 4 5
C
7
0
333200
1 2 3 4 5 6 7 8
B
74320
1 2 3 4 5
C
8
0
53332200
1 2 3 4 5 6 7 8
B
11
COUNTING-SORT
Alg.: COUNTING-SORT(A, B, n, k)
1. for i ← 0 to r
2. do C[ i ] ← 0
3. for j ← 1 to n
4. do C[A[ j ]] ← C[A[ j ]] + 1
5. C[i] contains the number of elements equal to i
6. for i ← 1 to r
7. do C[ i ] ← C[ i ] + C[i -1]
8. C[i] contains the number of elements ≤ i
9. for j ← n downto 1
10. do B[C[A[ j ]]] ← A[ j ]
11. C[A[ j ]] ← C[A[ j ]] - 1
1 n
0 k
A
C
1 n
B
j
12
Analysis of Counting Sort
Alg.: COUNTING-SORT(A, B, n, k)
1. for i ← 0 to r
2. do C[ i ] ← 0
3. for j ← 1 to n
4. do C[A[ j ]] ← C[A[ j ]] + 1
5. C[i] contains the number of elements equal to i
6. for i ← 1 to r
7. do C[ i ] ← C[ i ] + C[i -1]
8. C[i] contains the number of elements ≤ i
9. for j ← n downto 1
10. do B[C[A[ j ]]] ← A[ j ]
11. C[A[ j ]] ← C[A[ j ]] - 1
O(r)
O(n)
O(r)
O(n)
Overall time: O(n + r)
13
Analysis of Counting Sort
• Overall time: O(n + r)
• In practice we use COUNTING sort when r = O(n)
running time is O(n)
14
Radix Sort
• Represents keys as d-digit numbers in some
base-k
key = x
1
x
2
...x
d
where 0≤x
i
≤k-1
• Example: key=15
key
10
= 15, d=2, k=10 where 0≤x
i
≤9
key
2
= 1111, d=4, k=2 where 0≤x
i
≤1
15
Radix Sort
• Assumptions
d=O(1) and k =O(n)
• Sorting looks at one column at a time
– For a d digit number, sort the least significant
digit first
– Continue sorting on the next least significant
digit, until all digits have been sorted
– Requires only d passes through the list
16
RADIX-SORT
Alg.: RADIX-SORT(A, d)
for i ← 1 to d
do use a stable sort to sort array A on digit i
(stable sort: preserves order of identical elements)
17
Analysis of Radix Sort
• Given n numbers of d digits each, where each
digit may take up to k possible values, RADIX-
SORT correctly sorts the numbers in O(d(n+k))
– One pass of sorting per digit takes O(n+k) assuming
that we use counting sort
– There are d passes (for each digit)
18
Analysis of Radix Sort
• Given n numbers of d digits each, where each
digit may take up to k possible values, RADIX-
SORT correctly sorts the numbers in O(d(n+k))
– Assuming d=O(1) and k=O(n), running time is O(n)
19
Bucket Sort
• Assumption:
– the input is generated by a random process that distributes
elements uniformly over [0, 1)
• Idea:
– Divide [0, 1) into k equal-sized buckets (k=Θ(n))
– Distribute the n input values into the buckets
– Sort each bucket (e.g., using quicksort)
– Go through the buckets in order, listing elements in each one
• Input: A[1 . . n], where 0 ≤ A[i] < 1 for all i
• Output: elements A[i] sorted
20
Example - Bucket Sort
.78
.17
.39
.26
.72
.94
.21
.12
.23
.68
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
10
.21
.12 /
.72 /
.23 /
.78
.94 /
.68 /
.39 /
.26
.17
/
/
/
/
A
B
Distribute
Into buckets
21
Example - Bucket Sort
0
1
2
3
4
5
6
7
8
9
.23
.17 /
.78 /
.26 /
.72
.94 /
.68 /
.39 /
.21
.12
/
/
/
/
Sort within each
bucket
22
Example - Bucket Sort
0
1
2
3
4
5
6
7
8
9
.23
.17 /
.78 /
.26 /
.72
.94 /
.68 /
.39 /
.21
.12
/
/
/
/
.17.12 .23 .26
.21
.39 .68 .78.72 .94 /
Concatenate the lists from
0 to n – 1 together, in order
23
Analysis of Bucket Sort
Alg.: BUCKET-SORT(A, n)
for i ← 1 to n
do insert A[i] into list B[nA[i]]
for i ← 0 to k - 1
do sort list B[i] with quicksort sort
concatenate lists B[0], B[1], . . . , B[n -1]
together in order
return the concatenated lists
O(n)
k O(n/k log(n/k))
=O(nlog(n/k)
O(k)
O(n) (if k=Θ(n))
24
Radix Sort as a Bucket Sort
CSE408
Heap & Heap sort,Hashing
Lecture #18
Special Types of Trees
• Def: Full binary tree = a
binary tree in which each
node is either a leaf or has
degree exactly 2.
• Def: Complete binary tree = a
binary tree in which all leaves
are on the same level and all
internal nodes have degree 2.
Full binary tree
2
14 8
1
16
7
4
3
9 10
12
Complete binary tree
2
1
16
4
3
9 10
Definitions
• Height of a node = the number of edges on the longest
simple path from the node down to a leaf
• Level of a node = the length of a path from the root to
the node
• Height of tree = height of root node
2
14 8
1
16
4
3
9 10
Height of root = 3
Height of (2)= 1
Level of (10)= 2
Useful Properties
2
14 8
1
16
4
3
9 10
Height of root = 3
Height of (2)= 1
Level of (10)= 2
height
height
1
1
0
21
2 2 1
21
d
d
ld
l
n
+
+
=
−
= = −
−
(see Ex 6.1-2, page 129)
The Heap Data Structure
• Def: A heap is a nearly complete binary tree with
the following two properties:
– Structural property: all levels are full, except
possibly the last one, which is filled from left to right
– Order (heap) property: for any node x
Parent(x) ≥ x
Heap
5
7
8
4
2
From the heap property, it
follows that:
“The root is the maximum
element of the heap!”
A heap is a binary tree that is filled in order
Array Representation of Heaps
• A heap can be stored as an
array A.
– Root of tree is A[1]
– Left child of A[i] = A[2i]
– Right child of A[i] = A[2i + 1]
– Parent of A[i] = A[ i/2 ]
– Heapsize[A] ≤ length[A]
• The elements in the subarray
A[(n/2+1) .. n] are leaves
Heap Types
• Max-heaps (largest element at root), have the
max-heap property:
– for all nodes i, excluding the root:
A[PARENT(i)] ≥ A[i]
• Min-heaps (smallest element at root), have the
min-heap property:
– for all nodes i, excluding the root:
A[PARENT(i)] ≤ A[i]
Adding/Deleting Nodes
• New nodes are always inserted at the bottom
level (left to right)
• Nodes are removed from the bottom level (right
to left)
Operations on Heaps
• Maintain/Restore the max-heap property
– MAX-HEAPIFY
• Create a max-heap from an unordered array
– BUILD-MAX-HEAP
• Sort an array in place
– HEAPSORT
• Priority queues
Maintaining the Heap Property
• Suppose a node is smaller than a
child
– Left and Right subtrees of i are max-heaps
• To eliminate the violation:
– Exchange with larger child
– Move down the tree
– Continue until node is not smaller than
children
Example
MAX-HEAPIFY(A, 2, 10)
A[2] violates the heap property
A[2] A[4]
A[4] violates the heap property
A[4] A[9]
Heap property restored
Maintaining the Heap Property
• Assumptions:
– Left and Right
subtrees of i are
max-heaps
– A[i] may be
smaller than its
children
Alg: MAX-HEAPIFY(A, i, n)
1. l ← LEFT(i)
2. r ← RIGHT(i)
3. if l ≤ n and A[l] > A[i]
4. then largest ←l
5. else largest ←i
6. if r ≤ n and A[r] > A[largest]
7. then largest ←r
8. if largest i
9. then exchange A[i] ↔ A[largest]
10. MAX-HEAPIFY(A, largest, n)
MAX-HEAPIFY Running Time
• Intuitively:
• Running time of MAX-HEAPIFY is O(lgn)
• Can be written in terms of the height of the heap,
as being O(h)
– Since the height of the heap is lgn
h
2h
O(h)
-
-
-
-
Building a Heap
Alg: BUILD-MAX-HEAP(A)
1. n = length[A]
2. for i ← n/2 downto 1
3. do MAX-HEAPIFY(A, i, n)
• Convert an array A[1 … n] into a max-heap (n = length[A])
• The elements in the subarray A[(n/2+1) .. n] are leaves
• Apply MAX-HEAPIFY on elements between 1 and n/2
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
4 1 3 2 16 9 10 14 8 7
A:
Example: A
4 1 3 2 16 9 10 14 8 7
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
1
16
7
4
10
9 3
1
2 3
4 5 6 7
8 9 10
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
16
7
1
4
10
9 3
1
2 3
4 5 6 7
8 9 10
8
2 4
14
7
1
16
10
9 3
1
2 3
4 5 6 7
8 9 10
i = 5 i = 4 i = 3
i = 2 i = 1
Running Time of BUILD MAX HEAP
Running time: O(nlgn)
• This is not an asymptotically tight upper bound
Alg: BUILD-MAX-HEAP(A)
1. n = length[A]
2. for i ← n/2 downto 1
3. do MAX-HEAPIFY(A, i, n)
O(lgn)
O(n)
Running Time of BUILD MAX HEAP
• HEAPIFY takes O(h) the cost of HEAPIFY on a node i is
proportional to the height of the node i in the tree
Height Level
h
0
= 3 (lgn)
h
1
= 2
h
2
= 1
h
3
= 0
i = 0
i = 1
i = 2
i = 3 (lgn)
No. of nodes
2
0
2
1
2
2
2
3
h
i
= h – i height of the heap rooted at level i
n
i
= 2
i
number of nodes at level i
i
h
i
i
hnnT
=
=
0
)(
( )
ih
h
i
i
−=
=0
2
)(nO=
Running Time of BUILD MAX HEAP
i
h
i
i
hnnT
=
=
0
)(
Cost of HEAPIFY at level i number of nodes at that level
( )
ih
h
i
i
−=
=0
2
Replace the values of n
i
and h
i
computed before
h
h
i
ih
ih
2
2
0
=
−
−
=
Multiply by 2
h
both at the nominator and denominator and
write 2
i
as
i−
2
1
=
=
h
k
k
h
k
0
2
2
Change variables: k = h - i
=
0
2
k
k
k
n
The sum above is smaller than the sum of all elements to
and h = lgn
)(nO=
The sum above is smaller than 2
Running time of BUILD-MAX-HEAP: T(n) = O(n)
Heapsort
• Goal:
– Sort an array using heap representations
• Idea:
– Build a max-heap from the array
– Swap the root (the maximum element) with the last
element in the array
– “Discard” this last node by decreasing the heap size
– Call MAX-HEAPIFY on the new root
– Repeat this process until only one node remains
Example: A=[7, 4, 3, 1, 2]
MAX-HEAPIFY(A, 1, 4) MAX-HEAPIFY(A, 1, 3) MAX-HEAPIFY(A, 1, 2)
MAX-HEAPIFY(A, 1, 1)
Alg: HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. MAX-HEAPIFY(A, 1, i - 1)
• Running time: O(nlgn) --- Can be
shown to be Θ(nlgn)
O(n)
O(lgn)
n-1 times
Priority Queues
12
4
Operations on Priority Queues
• Max-priority queues support the following
operations:
– INSERT(S, x): inserts element x into set S
– EXTRACT-MAX(S): removes and returns element of
S with largest key
– MAXIMUM(S): returns element of S with largest key
– INCREASE-KEY(S, x, k): increases value of element
x’s key to k (Assume k ≥ x’s current key value)
HEAP-MAXIMUM
Goal:
– Return the largest element of the heap
Alg: HEAP-MAXIMUM(A)
1. return A[1]
Running time: O(1)
Heap A:
Heap-Maximum(A) returns 7
HEAP-EXTRACT-MAX
Goal:
– Extract the largest element of the heap (i.e., return the max
value and also remove that element from the heap
Idea:
– Exchange the root element with the last
– Decrease the size of the heap by 1 element
– Call MAX-HEAPIFY on the new root, on a heap of size n-1
Heap A:
Root is the largest element
Example: HEAP-EXTRACT-MAX
8
2 4
14
7
1
16
10
9 3
max = 16
8
2 4
14
7
1
10
9 3
Heap size decreased with 1
4
2 1
8
7
14
10
9 3
Call MAX-HEAPIFY(A, 1, n-1)
HEAP-EXTRACT-MAX
Alg: HEAP-EXTRACT-MAX(A, n)
1. if n < 1
2. then error “heap underflow”
3. max ← A[1]
4. A[1] ← A[n]
5. MAX-HEAPIFY(A, 1, n-1) remakes heap
6. return max
Running time: O(lgn)
HEAP-INCREASE-KEY
• Goal:
– Increases the key of an element i in the heap
• Idea:
– Increment the key of A[i] to its new value
– If the max-heap property does not hold anymore:
traverse a path toward the root to find the proper
place for the newly increased key
8
2 4
14
7
1
16
10
9 3
i
Key [i] ← 15
Example: HEAP-INCREASE-KEY
14
2 8
15
7
1
16
10
9 3
i
8
2 4
14
7
1
16
10
9 3
i
Key [i ] ← 15
8
2 15
14
7
1
16
10
9 3
i
15
2 8
14
7
1
16
10
9 3
i
HEAP-INCREASE-KEY
Alg: HEAP-INCREASE-KEY(A, i, key)
1. if key < A[i]
2. then error “new key is smaller than current key”
3. A[i] ← key
4. while i > 1 and A[PARENT(i)] < A[i]
5. do exchange A[i] ↔ A[PARENT(i)]
6. i ← PARENT(i)
• Running time: O(lgn)
8
2 4
14
7
1
16
10
9 3
i
Key [i] ← 15
-
MAX-HEAP-INSERT
• Goal:
– Inserts a new element into a max-
heap
• Idea:
– Expand the max-heap with a new
element whose key is -
– Calls HEAP-INCREASE-KEY to
set the key of the new node to its
correct value and maintain the
max-heap property
8
2 4
14
7
1
16
10
9 3
15
8
2 4
14
7
1
16
10
9 3
Example: MAX-HEAP-INSERT
-
8
2 4
14
7
1
16
10
9 3
Insert value 15:
- Start by inserting -
15
8
2 4
14
7
1
16
10
9 3
Increase the key to 15
Call HEAP-INCREASE-KEY on A[11] = 15
7
8
2 4
14
15
1
16
10
9 3
7
8
2 4
15
14
1
16
10
9 3
The restored heap containing
the newly added element
MAX-HEAP-INSERT
Alg: MAX-HEAP-INSERT(A, key, n)
1. heap-size[A] ← n + 1
2. A[n + 1] ← -
3. HEAP-INCREASE-KEY(A, n + 1, key)
Running time: O(lgn)
-
8
2 4
14
7
1
16
10
9 3
Summary
• We can perform the following operations on
heaps:
– MAX-HEAPIFY O(lgn)
– BUILD-MAX-HEAP O(n)
– HEAP-SORT O(nlgn)
– MAX-HEAP-INSERT O(lgn)
– HEAP-EXTRACT-MAX O(lgn)
– HEAP-INCREASE-KEY O(lgn)
– HEAP-MAXIMUM O(1)
Average
O(lgn)
Hash Functions
• If the input keys are integers then simply Key
mod TableSize is a general strategy.
– Unless key happens to have some undesirable
properties. (e.g. all keys end in 0 and we use mod 10)
• If the keys are strings, hash function needs more
care.
– First convert it into a numeric value.
Some methods
• Truncation:
– e.g. 123456789 map to a table of 1000 addresses
by picking 3 digits of the key.
• Folding:
– e.g. 123|456|789: add them and take mod.
• Key mod N:
– N is the size of the table, better if it is prime.
• Squaring:
– Square the key and then truncate
• Radix conversion:
– e.g. 1 2 3 4 treat it to be base 11, truncate if
necessary.
Hash Function 1
• Add up the ASCII values of all characters of the key.
int hash(const string &key, int tableSize)
{
int hasVal = 0;
for (int i = 0; i < key.length(); i++)
hashVal += key[i];
return hashVal % tableSize;
}
• Simple to implement and fast.
• However, if the table size is large, the function does not distribute the
keys well.
• e.g. Table size =10000, key length <= 8, the hash function
can assume values only between 0 and 1016
Hash Function 2
• Examine only the first 3 characters of the key.
int hash (const string &key, int tableSize)
{
return (key[0]+27 * key[1] + 729*key[2]) % tableSize;
}
• In theory, 26 * 26 * 26 = 17576 different words can be generated.
However, English is not random, only 2851 different combinations are
possible.
• Thus, this function although easily computable, is also not appropriate if
the hash table is reasonably large.
Hash Function 3
int hash (const string &key, int tableSize)
{
int hashVal = 0;
for (int i = 0; i < key.length(); i++)
hashVal = 37 * hashVal + key[i];
hashVal %=tableSize;
if (hashVal < 0) /* in case overflows occurs */
hashVal += tableSize;
return hashVal;
};
−
=
−−=
1
0
37]1[)(
KeySize
i
i
iKeySizeKeykeyhash
Hash function for strings:
a l i
key
KeySize = 3;
98
108
105
hash(“ali”) = (105 * 1 + 108*37 + 98*37
2
) % 10,007 = 8172
0 1 2
i
key[i]
hash
function
ali
……
……
0
1
2
8172
10,006 (TableSize)
“ali”
Double Hashing
• A second hash function is used to drive the
collision resolution.
– f(i) = i * hash
2
(x)
• We apply a second hash function to x and probe
at a distance hash
2
(x), 2*hash
2
(x), … and so on.
• The function hash
2
(x) must never evaluate to
zero.
– e.g. Let hash
2
(x) = x mod 9 and try to insert 99 in the
previous example.
• A function such as hash
2
(x) = R – ( x mod R)
with R a prime smaller than TableSize will work
well.
– e.g. try R = 7 for the previous example.(7 - x mode 7)
Hashing Applications
• Compilers use hash tables to implement the
symbol table (a data structure to keep track of
declared variables).
• Game programs use hash tables to keep track of
positions it has encountered (transposition table)
• Online spelling checkers.
Summary
• Hash tables can be used to implement the insert
and find operations in constant average time.
– it depends on the load factor not on the number of
items in the table.
• It is important to have a prime TableSize and a
correct choice of load factor and hash function.
• For separate chaining the load factor should be
close to 1.
• For open addressing load factor should not
exceed 0.5 unless this is completely
unavoidable.
– Rehashing can be implemented to grow (or shrink)
the table.
CSE408
Lower bound theory
Lecture # 31
Lower bound
• We always consider the algorithm with
smaller order of complexity as the better.
• How can we ensure that is there any faster
method available
• We need to find a function g(n) which is a
lower bound on the time that algorithm must
take, So if f(n) is the time for some algorithm
then we can write f(n)=Ω(g(n) where g(n) is
lower bound for f(n)
Lower bound theory
• Or we can say f(n) >= c * g(n) for all n>n0
• Where c & n0 are constants
• For many problems it is easy to calculate the
lower bound on n inputs
• e.g. consider the set of problems to find the
maximum of an ordered set of n integers. Clearly
every integer must be examined at least once. So
Ω(n) is a lower bound for that. For matrix
multiplication we have 2n2inputs so the lower
bound can be Ω(n2)
Sorting and Searching
• For all sorting & searching we use comparison
trees for finding the lower bound.
• For an unordered set the searching algorithm will
take Ω(n) as the lower bound. For an ordered set
it will take
• Ω(logn) as the lower bound. Similarly all the
sorting algorithms can not sort in less then
Ω(nlogn) time so Ω(nlogn) is the lower bound for
sorting algorithms.
Oracle and adversary arguments
• Given some computational model, the oracle tells
the outcome of each comparison. In order to
derive a good lower bound, the oracle tries its
best to cause the algorithm to work as hard as it
might.
• Take the example of a tournament where the
values are called players and the largest value is
interpreted as the winner and the second largest
is taken as the runner up. So the problem is the
similar to finding the largest and the second
largest number out of a set of n numbers.
Second largest
• Since we can’t determine the second largest
element without having determined the
largest element, at least n-1 comparisons are
necessary. We need to show that there is
always some sequence of comparisons which
forces the second largest to be fund in (logn)-1
additional comparisons
Tournament theory
• The winner of the tournament has played x matches then
there are x people who are candidates for the runner up
position. The runner up has lost only once to the winner
and other x-1 persons must have lost to one other person.
We can produce a oracle which decides the results of
matches in such a way that winner plays logn other people.
• In a match between a and b the oracle declares a as the
winner if a is previously undefeated and b has lost at least
once or if both a and b are undefeated but a has won more
match then b. In any other case the oracle can decide
arbitrarily as long as it remains consistent.
Winning match
• Corresponding to this tournament imagine
drawing a directed graph with n vertices. Each
vertex corresponds to one of the n players.
Draw a directed edge from vertex b to a iff
either player a has defeated b or a has
defeated another player who has defeated b.
Since for the overall winner there must be an
edge from each of the remaining n-1 vertices,
it follows that the winner must have played at
least logn matches.
Increasing matrix
• M is an nXn integer matrix in which the keys in
each row are in increasing order. Consider the
problem of finding the position of an integer x
in M. Determine a lower bound for the no. of
comparisons to be done in the problem.